GitHub@mujiu555's page

讲真话现在天天看晚上发电的都尴尬, 中二一笔.

多么想要, 知道如何活下去啊

Values, plain bits, expressed in high or low electronic levels, may represent some information. With corresponding context or encoding, together with its own properties, like name, can be then interpreted as real information, the data. Raw information, data, must have some way to be stored. And the way to translate original data into values can be stored in computer, it then called, "coding". Encoding converting data into a specific format or representation.

Coding help people understand data.

Most important part of a computer is CPU. CPU, central processing unit, controls almost all calculation process of computer.

And, further more, ALU, arithmetic logic unit, is kernel of CPU. The ALU is responsible for arithmetic and logical computations. Without an ALU, the CPU would be unable to perform its core operations.

Registers are another kernel of CPU, which provides ability for CPU to store data.

CU, front-end of a CPU, controls the behaviour of whole CPU. CU may fetch commands, do preprocessing and instruct command execution order. Preprocessing for commands can be PreDecode PreDecode , Decode Decode , Micro-Fusion Micro-Fusion / Macro-Fusion Macro-Fusion , Branch Prediction Branch Prediction and Static Prediction Static Prediction .

To boost execution for float point number calculation, some CPU may also have FPU, floating point unit.

Memory access is another function a CPU must have, so, AGU, address generation unit, or ACU, address calculation unit, will help CPU calculating address offset of main memory.

MMU, memory management unit, a control unit maybe outside CPU, controls memory, maps logical memory from to physical address.

TLB, translation lookaside buffer, a critical cache for memory management, every time CPU try to map and fetch data from memory, it may visit TLB, so that memory address translation may speed up by checking existing mapping entry.

Cache, a general purpose buffer for data fetch from memory, once data caches, it can be access much faster than other data still exist only in main memory later. When data accessed, changed and used, it may also be written back to memory when every thing finished.

Use less memory with limited ability of computation.

Each have different

• Stats: ${𝑞}_1,{𝑞}_2,{𝑞}_3$
• Transitions: $\stackrel{1}{\to }$
• Start State:
• Accepted state:

Give finite string as input, and have output of accepted or reject.

Begin at start state, read input symbols, follow corresponding transitions, Accept if end with accept state, Reject if not.

We say that "M_1 accepts exactly those string in A where $𝐴=\left\{𝑤|𝑤\text{ contains substing 11}\right\}$". And, we have A that is the language accepted by the language $𝐿\left({𝑀}_1\right)$. ${𝑀}_1$ recognize A and $𝐴=𝐿\left({𝑀}_1\right)$.

Let A, B be languages:

• Union: $𝐴\cup 𝐵=\left\{𝑤|𝑤\in 𝐴\vee 𝑤\in 𝐵\right\}$,
• Concatenation: $𝐴○𝐵=\left\{𝑥𝑦|𝑥\in 𝐴\wedge 𝑦\in 𝐵\right\}=𝐴𝐵$,
• Kleene Star: Unary operation: ${𝐴}^{\ast }=\left\{{𝑥}_1\dots {𝑥}_{𝑘}|\text{ each }{𝑥}_{𝑖}\in 𝐴\text{ for }𝑘\ge 0\right\},𝜀\in {𝐴}^{\ast }$

Note., empty language won't accept empty string, but Kleene star of empty language will.

Like mathematical expression comes from combination of mathematical operations and mathematical elements, regular expression comes form combination of regular operations and languages.

• Built form $\mathrm{\Sigma }$ (Alphabet), members $\mathrm{\Sigma }$, $\varnothing$ (Empty language), $𝜀$ (empty word), [atomic]
• Using $\cup$, $○$, $\ast$, [Composite]

E.g., ${\left(0\cup 1\right)}^{\ast }={\mathrm{\Sigma }}^{\ast }$ gives all strings over $\mathrm{\Sigma }$.

Finite automata equivalent to regular expressions.

If ${𝐴}_1,{𝐴}_2$ are regular languages, so is ${𝐴}_1\cup {𝐴}_2$ (closure under $\cup$)

Proof: let ${𝑀}_1=\left({𝑄}_1,\mathrm{\Sigma },{𝛿}_1,{𝑞}_1,{𝐹}_1\right)\text{ recognize }{𝐴}_1$,
and ${𝑀}_2=\left({𝑄}_2,\mathrm{\Sigma },{𝛿}_2,{𝑞}_2,{𝐹}_2\right)\text{ recognize }{𝐴}_2$.
Assuming $𝑀=\left(𝑄,\mathrm{\Sigma },𝛿,{𝑄}_0,𝐹\right)\text{ recognize }\left({𝐴}_1\cup {𝐴}_2\right)$,
$𝑀$ should accept input $𝑤$ if either ${𝑀}_1$ or ${𝑀}_2$ accept $𝑤$.

Compose ${𝑀}_1\text{ and }{𝑀}_2$ together, then components of M: $𝑄={𝑄}_1\times {𝑄}_2=\left\{\left({𝑞}_1,{𝑞}_2\right)|{𝑞}_1\in {𝑄}_1\text{ and }{𝑞}_2\in {𝑄}_2\right\}$, ${𝑞}_0=\left({𝑞}_1,{𝑞}_2\right)$ And, $𝛿\left(\left(𝑞,𝑟\right),𝑎\right)=\left({𝛿}_1\left(𝑞,𝑎\right),{𝛿}_2\left(𝑟,𝑎\right)\right)$ $𝐹=\left({𝐹}_1\times {𝑄}_2\right)\cup \left({𝑄}_1\times {𝐹}_2\right)$

Note., if $𝐹={𝐹}_1\times {𝐹}_2$, then it could be closure under intersection.

If ${𝐴}_1,{𝐴}_2$ are regular languages, so is ${𝐴}_1○{𝐴}_2$ (closure under $○$)

Assuming $𝑀$ accept input $𝑤$, if $𝑤=𝑥𝑦$ where, ${𝑀}_1\text{ accepts }𝑥$ and ${𝑀}_2\text{ accepts }𝑦$ But failed.

Proof: Let ${𝑀}_1=\left({𝑄}_1,\mathrm{\Sigma },{𝛿}_1,{𝑞}_1,{𝐹}_1\right)\text{ recognize }{𝐴}_1$, and ${𝑀}_2=\left({𝑄}_2,\mathrm{\Sigma },{𝛿}_2,{𝑞}_2,{𝐹}_2\right)\text{ recognize }{𝐴}_2$. Construct $𝑀=\left(𝑄,\mathrm{\Sigma },𝛿,{𝑞}_0,𝐹\right)\text{ recognize }\left({𝐴}_1○{𝐴}_2\right)$.

Then the machine $𝑀$ should accept input $𝑤$ if there is a split of w into $𝑥𝑦$ where ${𝑀}_1$ accepts $𝑥$ and ${𝑀}_2$ accepts $𝑦$.

And then construct M:

If there are input word $𝑤$, then there should be a split point where ${𝑀}_1$ reach accept state and jump to ${𝑀}_2$ via $𝜀$ transition.

Construct a new machine, concatenating ${𝑀}_1$ and ${𝑀}_2$ together with $𝜀$ transitions from each accept state of ${𝑀}_1$ to the start state of ${𝑀}_2$.

But the first place machine reach accept state may not be the correct split point. M need to have a idea of all possible split points.

Defn: A nondeterministic finite automaton, 5-tuple $\left(𝑄,\mathrm{\Sigma },𝛿,{𝑞}_0,𝐹\right)$:

• Q: finite set of states
• $\mathrm{\Sigma }$: finite set of alphabet symbols
• $𝛿$: transition function $𝛿:𝑄\times {\mathrm{\Sigma }}_{𝜀}\left(\mathrm{\Sigma }\cup \left\{𝜀\right\}\right)\to 𝑃\left(𝑄\right)=\left\{𝑅|𝑅\subseteq 𝑄\right\}$ $𝛿$, a kind of relation, give a state and a accepted symbol (or epsilon), then returns a set of (maybe) new states. Eg. $𝛿\left(𝑞,𝑎\right)=\left\{𝑟,𝑠\right\}\Rightarrow$
• ${𝑞}_0$: start state
• $𝐹$: set of accept states

E.g., in above example:

• $𝛿\left({𝑞}_1,𝑎\right)=\left\{{𝑞}_1,{𝑞}_2\right\}$
• $𝛿\left({𝑞}_1,𝑏\right)=\varnothing$

Computation processes of NFA is a kind of BFS:

• Every time the machine read an input symbol, it will branch out to all possible next states.
• Every time the machine find a accept state, it will accept the input immediately. Which discard all other possible paths.

Or, you may image the machine can make good guesses at each step, which always choose the correct transition to reach accept state if there is one.

Theorem: If an NFA recognizes a language L, then L is regular.

Proof: Let NFA $𝑀=<𝑄,\mathrm{\Sigma },𝛿,{𝑞}_0,𝐹>$ recognize L.
Construct DFA ${𝑀}^{\prime }=<{𝑄}^{\prime },\mathrm{\Sigma },{𝛿}^{\prime },{𝑞}_{0^{\prime }},{𝐹}^{\prime }>$

Basically, DFA ${𝑀}^{\prime }$ keeps track of the subset of states in NFA $𝑀$. Simulate the processes of NFA, every time the symbol is read, DFA ${𝑀}^{\prime }$ update its state to the set of possible states that NFA $𝑀$ may reach.

The way to archieve this is to set a state for every possible subset of states in NFA $𝑀$. For each state in DFA ${𝑀}^{\prime }$, which is a possible subset of states in NFA $𝑀$, remember which subset of states NFA in.

Construction of DFA ${𝑀}^{\prime }$:

• ${𝑄}^{\prime }=𝑃\left(𝑄\right)=\left\{𝑅|𝑅\subseteq 𝑄\right\}$, the set of all possible subsets of states in NFA $𝑀$.
• ${𝛿}^{\prime }\left(𝑅,𝑎\right)=\left\{𝑞|𝑞\in 𝛿\left(𝑟,𝑎\right)\text{ for some }𝑟\in 𝑅\right\},𝑅\in 𝑄$
• ${𝑞}_{0^{\prime }}=\left\{{𝑞}_0\right\}$
• ${𝐹}^{\prime }=\left\{𝑅\in {𝑄}^{\prime }|𝑅\cap 𝐹\right\}$

Then, DFA ${𝑀}^{\prime }$ simulates NFA $𝑀$ by keeping track of all possible states that NFA $𝑀$ may reach after reading input string.

From the construction, Start at the state $\left\{{𝑞}_0\right\}$ in NFA ${𝑀}^{\prime }$, which corresponds to the start state ${𝑞}_0$ in DFA $𝑀$, try to attach all possible states that NFA $𝑀$ may reach after reading input string, Thus a subset of states in NFA $𝑀$ can be formed, which is a state in DFA ${𝑀}^{\prime }$. Then start at each state in NFA $𝑀$, follow the same rule, try all possible transitions for each input symbol, construct new subset of states in NFA $𝑀$, which is a new state in DFA ${𝑀}^{\prime }$. Then start at each new constructed subsets, search all possible transitions for each input symbol with each state in the subset.

• If any one of the state can reach an new state, then add that new state into the new subset.
• If any one of the state in the subset is an accept state in NFA $𝑀$, then the new subset is also an accept state in DFA ${𝑀}^{\prime }$.

Recursely do this until no new subsets can be formed.

P.S., with this construction, some states in DFA ${𝑀}^{\prime }$ may be unreachable from the start state $\left\{{𝑞}_0\right\}$, discard those states. With this construction, some states in DFA may not able to reach any accept states, those states can be considered as dead states. Discard those or keep those states as you like.

P.S., If any one of the state have epsilon transitions, then add those reachable states via epsilon transitions into the subset as well.

E.g., for NFA above:

Since no branch sketch to dead state $\left\{{𝑞}_2\right\}$ or $\left\{{𝑞}_3\right\}$ or $\left\{{𝑞}_4\right\}$, those states can be discarded.

Which have a image like:

• Union: Construct a new NFA that connect two start states of two NFA via epsilon transitions from a new start state. And then everything done.
• Concatenation: Construct a new NFA that connect each accept state of first NFA to the start state of second NFA via epsilon transitions. And then everything done.
• Star: Construct a new NFA that connect each accept state of NFA back to the start state via epsilon transitions. Also, add a new start state that is also an accept state, and connect it to the old start state via epsilon transition. And then everything done.

Theorem: If R is a regexpr and $𝐴=𝐿\left(𝑅\right)$ then A is regular.

Proof:

Basically, Convert R to equivalent NFA $𝑀$,

• If R is atomic:

  • $𝑅=𝑎\text{ for a symbol }𝑎\in \mathrm{\Sigma }$:
  • $𝑅=𝜀$: or
  • $𝑅=\varnothing$:

• If R is composite:

  • $𝑅={𝑅}_1\cup {𝑅}_2$: for and , exists
  • $𝑅={𝑅}_1○{𝑅}_2$: for and , exists
  • $𝑅={𝑅}_1^{\ast }$: for , exists

Then, by structural induction on R, we can show that NFA $𝑀$ recognizes A.

Similar to NFA, but will more complex transitions. GNFA allow transitions labeled with regular expressions.

Assume:

• one accept state, separate from the start state: connect all old accept states to new accept state via epsilon transitions, and treat old accept states as normal states.

• one arrow from each state to each state, except:

  • only existing the start state
  • only entering the accept state
  • connect states without stransitions via emptyset transitions.

Inverse, if a language L is regular, then there is a regexpr R such that $𝐿=𝐿\left(𝑅\right)$.

Lemma: Every GNFA G has an equivalent regular expression R.

Proof:

By induction on the number of states in GNFA G.

Basic(k = 2): G = . Let R = r

Induction step(k > 2): Assume Lemma true for k - 1 states and prove for k states.

Convert k-state GNFA G to (k - 1)-state GNFA G' by removing one state q_rip that neither start nor accept states. And repair all path may go through q_rip.

To show a language is regular, just give a finite automaton or a regular expression.

To show a language is non-regular, give a proof by contradiction with pumping lemma.

Pumping lemma for regular languages describes a property that all regular languages must satisfy. If a language fail to satisfy this property, then it is non-regular.

Pumping Lemma: For every regular language A, there is a number p (the pumping length) such that if $𝑠\in 𝐴\wedge \left|𝑠\right|\ge 𝑝$ then $𝑠=𝑥𝑦𝑧$ where

• $𝑥{𝑦}^{𝑖}𝑧\in 𝐴$ for all $𝑖\ge 0$,
• $𝑦\ne 𝜀$ (y is not empty),
• $|𝑥𝑦|\le 𝑝$,

Informally, any sufficiently long string in a regular language can be pumped (have a middle section repeated any number of times) and still be in the language.

Or, If there is a substring that can be repeated any number of times to produce new strings in the language, then the language may be regular.

Pumping lemma depends on the fact that if M has p states, and it runs for more than p steps will enter some state at least twice (by pigeonhole principle).

Start at the root with start variable, then for each rule applied, create child nodes for each symbol in the right side of the rule.

When all leaves are terminals, the parse tree is complete.

Defn: A context-free grammar G is a 4-tuple $\left(𝑉,\mathrm{\Sigma },𝑅,𝑆\right)$ where

• V: finite set of variables
• $\mathrm{\Sigma }$: finite set of terminal symbols, disjoint from V
• R: finite set of rules of the form $𝐴\to 𝛾$ where $𝐴\in 𝑉$ and $𝛾\in {\left(𝑉\cup \mathrm{\Sigma }\right)}^{\ast }$
• S: start variable, $𝑆\in 𝑉$

For $𝑢,𝑣\in {\left(𝑉\cup \mathrm{\Sigma }\right)}^{\ast }$, we say that u directly derives v,

1. $𝑢\Rightarrow 𝑣$: u yield v if it can go from u to v in one substitution step in G
2. $𝑢\stackrel{\ast }{\Rightarrow }𝑣$: u yield v if it can go from u to v in zero or more substitution steps in G or $𝑢\Rightarrow {𝑢}_1\Rightarrow {𝑢}_2\Rightarrow \dots \Rightarrow 𝑣$, called derivation of v from u. If $𝑢=𝑆$, then it is a derivation of v from G.